package 剑指offer;

public class _19正则表达式匹配 {
	  public static boolean isMatch(String s, String p) {
	        if ((s==null&&p!=null)||(s!=null&&p==null)) return  false;
	        if(s==null&&p==null) return true;

	        int n=s.length(),m=p.length();
	        boolean [][]dp=new boolean[n+1][m+1];
	        dp[0][0]=true;
	        //首行为空字符串时，当“*”成偶数的出现也是匹配的
	        for (int j=2;j<=m;j+=2)
	            dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';

	        for (int i = 1; i <= n ; i++) {
	            for (int j = 1; j <= m; j++) {
	                dp[i][j]=p.charAt(j-1)=='*' ? dp[i][j-2]||dp[i][j-1]||dp[i-1][j]&&(s.charAt(i-1)==p.charAt(j-2)||p.charAt(j-2)=='.') :
	                        dp[i-1][j-1]&&(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='.');
	            }
	        }
	        return dp[n][m];
	    }

}
